摘要 :
We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the proper...
展开
We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer's well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation.
收起
摘要 :
An optimization problem is defined by an objective function to be maximized with respect to a set of constraints. To overcome some theoretical and practical difficulties, the constraint-set is sometimes relaxed and "easier" proble...
展开
An optimization problem is defined by an objective function to be maximized with respect to a set of constraints. To overcome some theoretical and practical difficulties, the constraint-set is sometimes relaxed and "easier" problems are solved. This led us to study relaxations providing exactly the same set of optimal solutions. We give a complete characterization of these relaxations and present several examples. While the relaxations introduced in this paper are not always easy to solve, they may help to prove that some mathematical programs are equivalent in terms of optimal solutions. An example is given where some of the constraints of a linear program can be relaxed within a certain limit.
收起
摘要 :
Offshore wind farms have boomed worldwide due to the sustainability of wind power and ocean resources. Power grid companies should consider the wind power consumption problem with more power generated. Power-flow calculation is th...
展开
Offshore wind farms have boomed worldwide due to the sustainability of wind power and ocean resources. Power grid companies should consider the wind power consumption problem with more power generated. Power-flow calculation is the most fundamental tool in energy management. This paper proposes the convex-relaxation-based method for offshore wind farms’ power flow. In this method, the traditional equations’ problem solving is transferred into standard convex optimization, which can be solved efficiently with unique optimum. Second-order cone relaxations are imposed to describe the quadratic relationship. The exactness of the relaxation is guaranteed with the special definition of the objective function.The superiority of the proposed method is tested on the case study, for which a computational efficiency improvement is shown. Moreover, the reliability of the power-flow results is verified within the precision tolerance.
收起
摘要 :
Deterministic global optimization is widely spread in the field of process engineering, e.g., for the solution of chemical equilibrium problems, heat exchanger networks, or process synthesis. The performance of state-of-the-art de...
展开
Deterministic global optimization is widely spread in the field of process engineering, e.g., for the solution of chemical equilibrium problems, heat exchanger networks, or process synthesis. The performance of state-of-the-art deterministic global optimization algorithms largely depends on the tightness of convex and concave relaxations. We propose results on relaxations of componentwise convex functions, i.e., functions that are convex with respect to each component when all other components are fixed. We show that if the partial derivatives of the original function satisfy a specific monotonicity condition, we can construct a valid underestimator of the original componentwise convex function. Concave relaxations of componentwise concave functions can be derived analogously. Finally, we show numerical examples and applications in property models, for example, the enthalpy of the subcooled liquid found in the IAPWS-IF97 model. The numerical result show drastic improvement in relaxation tightness when the proposed result is used compared to standard methods. (C) 2019 Elsevier Ltd. All rights reserved.
收起
摘要 :
Intrinsic volumes of convex sets are natural geometric quantities that also play important roles in applications, such as linear inverse problems with con, vex constraints, and constrained statistical inference. It is a well-known...
展开
Intrinsic volumes of convex sets are natural geometric quantities that also play important roles in applications, such as linear inverse problems with con, vex constraints, and constrained statistical inference. It is a well-known fact that, given a closed convex cone CC R-d, its conic intrinsic volumes determine a probability measure on the finite set (0, 1,...., d}, customarily denoted by L(V-C). The aim of the present paper is to provide a Berry Esseen bound for the normal approximation of L(V-C), implying a general quantitative central limit theorem (CLT) for sequences of (correctly normalised) discrete probability measures of the type C(V-Cn, n >= 1. This bound shows that, in the high-dimensional limit, most conic intrinsic volumes encountered in applications can be approximated by a suitable Gaussian distribution. Our approach is based on a variety of techniques, namely: (1) Steiner formulae for closed convex cones, (2) Stein's method and second-order Poincaro inequality, (3) concentration estimates and (4) Fourier analysis. Our results explicitly connect the sharp phase transitions, observed in many regularised linear inverse problems with convex constraints, with the asymptotic Gaussian fluctuations of the intrinsic volumes of the associated descent cones. In particular, our findings complete and further illuminate the recent breakthrough discoveries by Amelunxen, Lotz, McCoy and Tropp [Inf. Inference 3 (2014) 224-294] and McCoy and Tropp [Discrete Comput. Geom. 51 (2014) 926-963] about the concentration of conic intrinsic volumes and its connection with threshold phenomena. As an additional outgrowth of our work we develop total variation bounds for normal approximations of the lengths of projections of Gaussian vectors on closed convex sets.
收起
摘要 :
An integral representation result is obtained for the relaxation of a class of energy functionals depending on two vector fields with different behaviors which appear in the context of thermochemical equilibria and are related to ...
展开
An integral representation result is obtained for the relaxation of a class of energy functionals depending on two vector fields with different behaviors which appear in the context of thermochemical equilibria and are related to image decomposition models and directors theory in nonlinear elasticity.
收起
摘要 :
Constraint propagation techniques have heavily utilized interval arithmetic while the application of convex and concave relaxations has been mostly restricted to the domain of global optimization. Here, reverse McCormick propagati...
展开
Constraint propagation techniques have heavily utilized interval arithmetic while the application of convex and concave relaxations has been mostly restricted to the domain of global optimization. Here, reverse McCormick propagation, a method to construct and improve McCormick relaxations using a directed acyclic graph representation of the constraints, is proposed. In particular, this allows the interpretation of constraints as implicitly defining set-valued mappings between variables, and allows the construction and improvement of relaxations of these mappings. Reverse McCormick propagation yields potentially tighter enclosures of the solutions of constraint satisfaction problems than reverse interval propagation. Ultimately, the relaxations of the objective of a non-convex program can be improved by incorporating information about the constraints.
收起
摘要 :
The question of determining strong convex underestimators for nonlinear functions is theoretically and practically of major interest. Unfortunately, results along these lines are quite limited as very few general procedures are at...
展开
The question of determining strong convex underestimators for nonlinear functions is theoretically and practically of major interest. Unfortunately, results along these lines are quite limited as very few general procedures are at hand that can be applied to general classes of functions. In this paper we show how to reduce the question of determining a convex envelope to lower-dimensional optimization problems when the underlying function is indefinite and (n-1)-convex. Our structural result about this reduction technique enables us to give descriptions for the convex envelope of a variety of two-dimensional functions.
收起
摘要 :
We study the integral representation of relaxed functional in the multi-dimensional calculus of variations, for integrands which are finite in a convex bounded set with nonempty interior and infinite elsewhere.
摘要 :
The convergence of the algorithm for solving convex feasibility problem is studied by the method of sequential averaged and relaxed projections. Some results of H. H. Bauschke and J. M. Borwein are generalized by introducing new m...
展开
The convergence of the algorithm for solving convex feasibility problem is studied by the method of sequential averaged and relaxed projections. Some results of H. H. Bauschke and J. M. Borwein are generalized by introducing new methods. Examples illustrating these generalizations are given.
收起
原文获取